This invention relates to digital signal processing devices and, in particular, provides methods and apparatus for efficient digital processing of signals. The invention can be practiced in connection with any of a large number of digital signal generating devices, including, but not limited to, audio equipment, television cameras, electron microscopes, and radar.
Digital image processing devices are digital signal processors used to process signals generated, for example, by a television camera. Here the signals to be processed are referred to as images, and the individual digital values of the signals are referred to as pixels.
Digital image processing devices are used as a foundation on which to build machine vision devices, which are of great practical importance in industrial automation and other areas where machines must make decisions based on visual input. Such devices are typically used to locate patterns for alignment, to measure distances, angles, and other critical dimensions, to guide robots, to inspect the quality of manufactured items, and to identify unknown objects. The digital image processors upon which machine vision devices are built must perform a variety of computations rapidly and inexpensively, including convolution, correlation, normalized correlation, spatial averaging, histograms, projections, and spatial moments.
Convolution is used to enhance images for further processing. Correlation and normalized correlation, which are mathematically similar to convolution, provide the basis for locating and judging the quality of specific features in images of objects.
Spatial averaging is used to reduce the resolution of an image by averaging blocks of pixels. Spatial averaging is used to reduce Processing time in situations where portions of an image are over-resolved. It is also useful for noise reduction and allows trading off spatial resolution for intensity resolution.
A histogram gives the frequency of occurrence of each of the intensity values present in an image. Histograms are useful for computing various statistical properties of an image, including range, mean, and variance.
A projection of an image onto a line is computed by summing the image pixels in strips perpendicular to the line. Projections have a variety of uses, including efficient computation of spatial moments: area, center of mass, principal moments of inertia, and principal axes of inertia.
An image processing device used in a machine vision system must be able to process pixels very rapidly. To perform the above-described operations, and in particular, correlation and convolution, prior art devices rely on expensive, specialized hardware. The resulting high costs to the end users of the devices have slowed the introduction of machine vision systems into practical industrial applications.
There accordingly exists a need for a digital image processor that provides rapid yet inexpensive processing of images.
It is therefore an object of this invention to provide a method and apparatus for digital image processing that can process images rapidly, using simple and inexpensive hardware.
It is a further object of this invention to provide a method and apparatus for performing convolution, correlation, and normalized correlation that requires fewer arithmetic operations per pixel than prior art devices, and where the traditional multiplication operations are eliminated.